package linear_enumeration;

import java.util.LinkedList;

public class basic1588 {
    public int sumOddLengthSubarrays(int[] arr) {
        int len=arr.length;
        int sum=0;
        for(int i=0;i<len;i++) {
            //左边偶数个数*右边偶数个数+左边奇数个数*右边奇数个数
            sum+=arr[i]*((i/2+1)*((len-i-1)/2+1)+((i+1)/2)*((len-i)/2));
        }
        return sum;
    }


        public int sumOddLengthSubarrays1(int[] arr) {
            int res = 0;
            for (int x: arr) {
                res += x;
            }
            int n = arr.length;
            for (int num = 3; num <= n; num += 2 ) {
                //TODO:再看
                for (int i = 0; i + num - 1 < n; i ++ ) {
                    int j = i;
                    int c = 0;
                    //统计长度为n的
                    while (j < n && c < num) {
                        res += arr[j ++];
                        c ++;
                    }
                }
            }
            return res;
        }


    class Solution1 {
        public int sumOddLengthSubarrays(int[] arr) {
            int n = arr.length;
            int sum[] = new int[n + 1];
            //初始化前缀和
            for (int i = 1; i <= n; i ++ ) {
                sum[i] = sum[i - 1] + arr[i - 1];
            }
            int res = 0;
            for (int len = 1; len <= n; len += 2 ) {
                //枚举左端点，限制右端点不越界
                for (int l = 0; l + len - 1 < n; l ++ ) {
                    int r = l + len - 1;
                    //即为[l, r]区间和
                    res += sum[r + 1] - sum[l];
                }
            }
            return res;
        }
    }

//  CKG TODO 2023/5/12: 不适合使用回溯　因为要求必须是ｉ连续的元素　　而回溯求出来的是相对位置上奇数个数的组合
//    int count=0;
//
//     LinkedList<Integer> path=new LinkedList<Integer>();
//    public int sumOddLengthSubarrays2(int[] arr) {
//        backTrack(0,arr,0);
//        return count;
//    }
//
//
//    public  void  backTrack(int start,int[] arr,int sum){
//        if (start>arr.length){
//            return;
//        }
//
//        if (path.size()%2==1){
//            for (int a: path
//                 ) {
//                System.out.print(a+" ");
//            }
//            System.out.println("====================");
//            count+=sum;
//        }
//
//        for (int i = start; i <arr.length; i++) {
//            sum+=arr[i];
//            path.add(arr[i]);
//            backTrack(i+1,arr,sum);
//            path.removeLast();
//            sum-=arr[i];
//        }
//
//    }




    public static void main(String[] args) {
        basic1588 basic1588 = new basic1588();
        System.out.println(basic1588.sumOddLengthSubarrays1(new int[]{1, 4, 2}));
//        Solution solution = new basic1588().new Solution();
//        solution.sumOddLengthSubarrays(new int[]{1, 4, 2, 5, 3});

    }



}
